Corelab Seminar
2016-2017
George Barmpalias
Aspects of Chaitin's Omega
Abstract.
Suppose that you run a universal computer on a random program - each time the next bit is required by the machine, a coin-toss determines its value. The probability that this randomized machine will halt is known as the halting probability, or Chaitin's Omega. Gregory Chaitin also proved that Omega is an algorithmically random real number, i.e. the initial segments of its binary expansion are incompressible. Since his seminal work, many popular expositions have appeared mainly focusing on the metamathematical or philosophical significance of this number (or debating against it). At the same time, a rich mathematical theory exploring the properties of Chaitin’s Omega has been brewing in various technical papers, which quietly reveals the significance of this number to many aspects of contemporary algorithmic information theory. In this talk, based on a recent survey article, I will expose these developments and tell a story about Omega which outlines its multifaceted mathematical properties and roles in algorithmic randomness.